1859F - Teleportation in Byteland - CodeForces Solution

#include <bits/stdc++.h>
 
#define all(x) (x).begin(), (x).end()
 
using namespace std;
 
int nxt() {
	int x;
	cin >> x;
	return x;
}
 
const int N = 111'111;
vector<pair<int, int>> a[N];
const int L = 22;
long long p[L][N];
 
int jump[N];
int parent[N];
int h[N], tin[N], tout[N];
int timer;
 
void dfs(int v, int par = -1) {
	parent[v] = par;
	tin[v] = timer++;
	for (auto [u, w] : a[v]) {
		if (u == par) {
			continue;
		}
		for (int i = 0; i < L; ++i) {
			p[i][u] = p[i][v] + ((w - 1) >> i) + 1;
		}
		h[u] = h[v] + 1;
 
		if (h[v] - h[jump[v]] == h[jump[v]] - h[jump[jump[v]]]) {
			jump[u] = jump[jump[v]];
		} else {
			jump[u] = v;
		}
 
		dfs(u, v);
	}
	tout[v] = timer;
}
 
long long g[L][N];
 
bool is_par(int u, int v) {
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}
 
int lca(int u, int v) {
	while (!is_par(u, v)) {
		if (is_par(jump[u], v)) {
			u = parent[u];
		} else {
			u = jump[u];
		}
	}
	return u;
}
 
long long opt[2][L][N]; // k, v
long long def[2][L][N];
 
void remin(long long& x, long long y) {
	x = (x < y) ? x : y;
}
 
void solve() {
	int n = nxt(), t = nxt();
	for (int i = 0; i < n; ++i) {
		a[i] = {};
	}
	for (int i = 0; i < n - 1; ++i) {
		int u = nxt() - 1, v = nxt() - 1, w = nxt();
		a[u].push_back({v, w});
		a[v].push_back({u, w});
	}
 
	timer = 0;
	dfs(0);
 
	string courses;
	cin >> courses;
	for (int k = 1; k < L; ++k) {
		using T = pair<long long, int>;
		priority_queue<T, vector<T>, greater<T>> pq;
		for (int i = 0; i < n; ++i) {
			if (courses[i] == '1') {
				pq.push({g[k][i] = t * k, i});
			} else {
				g[k][i] = 1e18;
			}
		}
		while (!pq.empty()) {
			auto [dst, v] = pq.top();
			pq.pop();
			if (g[k][v] != dst) {
				continue;
			}
			for (auto [u, w] : a[v]) {
				auto ndst = dst + w + ((w - 1) >> k) + 1;
				if (g[k][u] > ndst) {
					pq.emplace(g[k][u] = ndst, u);
				}
			}
		}
	}
 
	vector<int> order(n);
	for (int i = 0; i < n; ++i) {
		order[tin[i]] = i;
	}
	for (int k = 1; k < L; ++k) {
		for (int i : order) {
			opt[0][k][i] = def[0][k][i] = g[k][i] - p[0][i] + p[k][i];
			opt[1][k][i] = def[1][k][i] = g[k][i] + p[0][i] - p[k][i];
			if (!i) {
				continue;
			}
			if (jump[i] == parent[i]) {
				int par = parent[i];
				remin(opt[0][k][i], def[0][k][par]);
				remin(opt[1][k][i], def[1][k][par]);
			} else {
				int par = parent[i];
				for (int t : {0, 1}) {
					remin(opt[t][k][i], opt[t][k][par]);
					remin(opt[t][k][i], opt[t][k][jump[par]]);
				}
			}
		}
	}
 
	auto f = [&](int t, int k, int v, int height) {
		long long res = def[t][k][v];
		while (v >= 0 && h[v] >= height) {
			if (h[jump[v]] >= height) {
				remin(res, opt[t][k][v]);
				v = v ? jump[v] : parent[v];
			} else {
				remin(res, def[t][k][v]);
				v = parent[v];
			}
		}
		return res;
	};
 
	int q = nxt();
	while (q--) {
		int u = nxt() - 1, v = nxt() - 1;
		int l = lca(u, v);
 
		long long ans = p[0][u] + p[0][v] - 2 * p[0][l];
		for (int k = 1; k < L; ++k) {
			ans = min({
				ans,
				p[0][u] + f(0, k, u, h[l]) - p[k][l] + p[k][v] - p[k][l],
				p[0][u] - p[0][l] + p[k][v] + f(1, k, v, h[l]) - p[0][l]
			});
		}
		cout << ans << "\n";
	}
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int t = nxt();
	while (t--) {
		solve();
	}
 
	return 0;
}